package com.mango.algorithm.sort;

import com.google.common.base.Stopwatch;

import java.util.Arrays;
import java.util.concurrent.TimeUnit;

/**
 * 归并排序
 * 空间复杂度：O(n)
 * 时间复杂度：O(nLogN)
 * 思路：
 * 1. 取数组中间的下标mid
 * 2. 先排左边部分sort(0,mid)
 * 3. 再排右边部分sort(mid+1,len)
 * 4. 如果left>=right,则退出
 * 5. 合并数组，保证顺序
 *
 * 例子：
 * old:[13, 7, 4, 6, 9, 24, 12]
 * merge:[13] + [7] = [7, 13]
 * merge:[4] + [6] = [4, 6]
 * merge:[7, 13] + [4, 6] = [4, 6, 7, 13]
 * merge:[9] + [24] = [9, 24]
 * merge:[9, 24] + [12] = [9, 12, 24]
 * merge:[4, 6, 7, 13] + [9, 12, 24] = [4, 6, 7, 9, 12, 13, 24]
 * result:[4, 6, 7, 9, 12, 13, 24]
 */
public class MergeSort {
    public static void main(String[] args) {
        Stopwatch sw = Stopwatch.createStarted();
        int[] nums = {13,7,4,6,9,24,12,5,5,6,3,4,7};
        System.out.println("old:"+Arrays.toString(nums));
        System.out.println("result:"+Arrays.toString(sort(nums))+"耗时:"+sw.elapsed(TimeUnit.MILLISECONDS)+"ms");

    }

    public static int[] sort(int[] nums){
        sort(nums,0,nums.length-1);
        return nums;
    }
    // 归并排序
    public static void sort(int[] nums,int left,int right){
        if (left >= right) {
            return;
        }
        // 取左右的中间下标
        int mid = (left + right) / 2;
        // 先排左边的一半
        sort(nums,left,mid);
        // 再排右边的一半
        sort(nums,mid+1,right);
        // 如果中间的大于右边的才合并，本来就是小于的是满足顺序的，不需要做合并
        //if(nums[mid] > nums[mid+1]){
            // 合并左右2个数组
            merge(nums,left,mid,right);
        //}
    }
    // 将arr[left...mid]和arr[mid+1...right]两部分进行归并
    private static void merge(int[] nums,int left,int mid,int right){
        int[] leftArr = Arrays.copyOfRange(nums,left,mid+1);
        int[] rightArr = Arrays.copyOfRange(nums,mid+1,right+1);

        int l = 0;
        int r = 0;
        int index = left;
        while(l <leftArr.length && r < rightArr.length){
            nums[index++] = leftArr[l] <= rightArr[r] ? leftArr[l++] : rightArr[r++];
        }
        while(l<leftArr.length){
            nums[index++] = leftArr[l++];
        }
        while (r<rightArr.length){
            nums[index++] = rightArr[r++];
        }
        System.out.println("merge:"+Arrays.toString(leftArr)+" + "+Arrays.toString(rightArr) + " = " + Arrays.toString(Arrays.copyOfRange(nums,left,right+1)));
    }
}
